#include <iostream>
#include <vector>
using namespace std;
typedef long long LL;
#define endl '\n'
const int N = 6e3 + 10;
const int MOD = 1610612741;
const int PM = MOD - 1;
typedef pair<LL, LL> PII;
LL fac_len[N];
LL gac_glen[N];
LL f[N];
int n; 
LL C[N][N];

LL qpow(LL a, LL b, LL MOD)
{
	LL ret = 1;
	while(b)
	{
		if(b & 1) ret = ret * a % MOD;
		b >>= 1;
		a = a * a % MOD;
	}
	return ret;
}

void init()
{
	fac_len[0] = 1;
	for(int i = 1; i <= n; i++) fac_len[i] = fac_len[i - 1] * i % PM;
	// vector<LL, vector<LL>> C(n + 1, vector<LL>(n + 1));
	for(int i = 0; i <= n; i++)
	{
		C[i][0] = 1;
		for(int j = 1; j <= i; j++)
		{
			C[i][j] =(C[i - 1][j] + C[i - 1][j - 1]) % PM;
		}
	}
	for(int mid = 1; mid <= n; mid++)
	{
		for(int len = 1; len <= n; len++)
		{
			// if(len % 2 == 1) f[mid] = (f[mid] + (C[mid - 1][len / 2] * C[n - mid][len / 2] % PM * fac_len[len] % PM * fac_len[n - len] % PM * (n - len + 1) % PM)) % PM;
			f[mid] = (f[mid] + (C[mid - 1][len / 2] * C[n - mid][len - (len / 2) - 1] % PM * fac_len[len] % PM * fac_len[n - len] % PM * (n - len + 1) % PM)) % PM;
		}
	}	
}

void solve() 
{
    cin >> n;
	init();
	LL ans = 1;
	// for(int i = 0;i <= n; i++) cout << gac_glen[i] << " ";
	for(int mid = 1; mid <= n; mid++)
	{
		ans = (ans * qpow(mid, f[mid], MOD)) % MOD;
	}
	cout << ans << endl;
}

int main()
{
    ios::sync_with_stdio(0), cin.tie(0), cout.tie(0);
    int T = 1;
	// cin >> T;
	while(T--)
	{
        solve();
	}
	return 0;
}